package com.shangguigu.linkedlist;

import com.leetcode.datastructure.ListNode;

/**
 * @author: ZhouBert
 * @date: 2019/10/10
 * @description: 约瑟夫环
 * 已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围，从编号为k的人开始报数，数到m的那个人出列；
 * 他的下一个人又从1开始报数，数到m的那个人又出列；
 * 依此规律重复下去，直到圆桌周围的人只有一个没有出列。假设n=1000,k=5,m=13,问剩下最后一个人编号。
 * <p>
 * https://blog.csdn.net/zy345293721/article/details/81749015
 */
public class JosephCircle {

	/**
	 * 约瑟夫环算法，经典求解，动态减去链表中元素
	 * 采用生成环 ListNode 单向链表
	 * @param numberN
	 * @param startNumberK
	 * @param numberM
	 * @return
	 */
	public static int josephProblem(int numberN, int startNumberK, int numberM) {
		///1.生成环 head 即环的头结点
		ListNode head=new ListNode(1);
		ListNode cur=head;
		///2.开始节点
		ListNode preStartNode=null;
		for (int i = 2; i <= numberN; i++) {
			if (i==startNumberK){
				preStartNode=cur;
			}

			cur.next=new ListNode(i);
			cur=cur.next;
			if(startNumberK==1&&i==numberN){
				preStartNode=cur;
			}
		}
		///成环
		cur.next=head;

		///3.进行删除
		///while (preStartNode.next!=preStartNode) -还是用一个 size 表示吧
		int size=numberN;
		while (size>1){
			///4.找到要删除节点的前节点
			for (int i = 0; i < numberM-1; i++) {
				preStartNode=preStartNode.next;
			}
			System.out.printf("%d \t",preStartNode.next.val);
			preStartNode.next=preStartNode.next.next;
			size--;
		}


		return preStartNode.val;
	}

	public static void main(String[] args) {
		//int lastNumber = josephProblem(1000, 5, 13);
		int lastNumber = josephProblem(5, 1, 2);
		System.out.println(lastNumber);
		//int lastNumber = josephProblem(10, 5, 13);
	}
}
